// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 13:42
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.ArrayList;


public class GetMinimumDifference {
    /**
     * 判断二叉排序树的后续节点-> 二叉排序树的当前节点和后续节点的差值局部最小
     * 二叉搜素树的最小节点没有前继节点，最大节点没有后继节点
     * <p>
     * Update: 中序遍历二叉搜索树
     */

    public int getMinimumDifference(TreeNode root) {
        // 相邻两个节点直接的差值绝对值取最小
        ArrayList<Integer> nodes = new ArrayList<>();
        inOrder(root, nodes);
        return getMinDiff(nodes);
    }

    /**
     * 获取给定列表中的元素之间的最小差值，列表已经按照升序排序
     *
     * @param nodes 列表
     * @return 最小差值
     */
    private int getMinDiff(ArrayList<Integer> nodes) {
        int min = Integer.MAX_VALUE;
        if (nodes.size() == 0) {
            // 传入的列表是空表
            return -1;
        }
        int i = 0;
        int j = 1;
        while (j < nodes.size()) {
            min = Math.min(min, Math.abs(nodes.get(i) - nodes.get(j)));
            ++i;
            ++j;
        }
        return min;
    }

    /**
     * 二叉树的中序遍历
     *
     * @param root  根节点
     * @param nodes 二叉搜索树中序遍历列表
     */
    private void inOrder(TreeNode root, ArrayList<Integer> nodes) {
        if (root == null) {
            return;
        }
        inOrder(root.left, nodes);
        nodes.add(root.val);
        inOrder(root.right, nodes);
    }


}
